package leetcode.editor.cn.dsa11_sort;
// 按奇偶排序数组 II

import java.util.Arrays;

public class SortArrayByParityIi922_2 {
    public static void main(String[] args) {
        Solution solution = new SortArrayByParityIi922_2().new Solution();
        int[] arr = {4,2,5,7};
        solution.sortArrayByParityII(arr);
        System.out.println(Arrays.toString(arr));
        int[] arr2 = {1,2,3,4,5,6,7,8};
        solution.sortArrayByParityII(arr2);
        System.out.println(Arrays.toString(arr2));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        /**
         * 题目变形：要求所有奇数的相对顺序保持不变，所有偶数的相对顺序也保持不变
         * 例如:
         * 输入：[4,2,5,7]
         * 输出：[4,5,2,7]
         * 解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 都改变了相对顺序，所以都不正确
         * @param A
         * @return
         */
        public int[] sortArrayByParityII(int[] A) {
            // 定义新数组，存放结果数据
            int[] ret = new int[A.length];
            int prime = 1, even = 0; // 定义奇数和偶数起始索引
            for (int i = 0; i < A.length; i++) {
                if ((A[i] & 1) == 0) {
                    ret[even] = A[i]; // 存放偶数
                    even += 2;
                } else {
                    ret[prime] = A[i]; // 存放奇数
                    prime += 2;
                }
            }
            return ret;
        }
    }
    //leetcode submit region end(Prohibit modification and deletion)
}
